{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Widest Pair of Indices With Equal Range Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: widestPairOfIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #范围和相等的最宽索引对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个 <strong>以0为索引</strong> 的二进制数组 <code>nums1</code> 和 <code>nums2</code> 。找出 <strong>最宽</strong> 的索引对 <code>(i, j)</code> ，使的&nbsp;<code>i &lt;= j</code>&nbsp;并且&nbsp;<code>nums1[i] + nums1[i+1] + ... + nums1[j] == nums2[i] + nums2[i+1] + ... + nums2[j]</code>。</p>\n",
    "\n",
    "<p><strong>最宽</strong> 的指标对是指在 <code>i </code>和<code> j </code>之间的 <strong>距离最大</strong> 的指标对。一对指标之间的 <strong>距离</strong> 定义为<code> j - i + 1</code> 。</p>\n",
    "\n",
    "<p>返回 <strong>最宽</strong> 索引对的 <strong>距离</strong> 。如果没有满足条件的索引对，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [1,1,0,1], nums2 = [0,1,1,0]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "如果i = 1, j = 3:\n",
    "Nums1 [1] + Nums1 [2] + Nums1[3] = 1 + 0 + 1 = 2。\n",
    "Nums2 [1] + Nums2 [2] + Nums2[3] = 1 + 1 + 0 = 2。\n",
    "i和j之间的距离是j - i + 1 = 3 - 1 + 1 = 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [0,1], nums2 = [1,1]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:\n",
    "</strong>If i = 1 and j = 1:\n",
    "nums1[1] = 1。\n",
    "nums2[1] = 1。\n",
    "i和j之间的距离是j - i + 1 = 1 - 1 + 1 = 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [0], nums2 = [1]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:\n",
    "</strong>没有满足要求的索引对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums1[i]</code>&nbsp;仅为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>.</li>\n",
    "\t<li><code>nums2[i]</code>&nbsp;仅为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [widest-pair-of-indices-with-equal-range-sum](https://leetcode.cn/problems/widest-pair-of-indices-with-equal-range-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [widest-pair-of-indices-with-equal-range-sum](https://leetcode.cn/problems/widest-pair-of-indices-with-equal-range-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,0,1]\\n[0,1,1,0]', '[0,1]\\n[1,1]', '[0]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a=collections.Counter()\n",
    "        a[0]=-1\n",
    "        now=0\n",
    "        res=0\n",
    "        for i in range(len(nums1)):\n",
    "            now+=nums1[i]-nums2[i]\n",
    "            if now in a:\n",
    "                res=max(res,i-a[now])\n",
    "            else:\n",
    "                a[now]=i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dic = defaultdict(int)\n",
    "        dic[0] = -1\n",
    "        s = ans = 0\n",
    "        for i in range(n):\n",
    "            s += nums1[i] - nums2[i]\n",
    "            if s in dic:\n",
    "                ans = max(ans, i - dic[s])\n",
    "            else:\n",
    "                dic[s] = i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和+哈希表\n",
    "    # 为了方便计算，我们将前缀和的差转换为差的前缀和，这样只要两数组差的前缀和出现重复时，重复的这一段即为我们要找的和相等的片段。\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a = collections.Counter()\n",
    "        a[0] =- 1\n",
    "        now = 0\n",
    "        res = 0\n",
    "        for i in range(len(nums1)):\n",
    "            now += nums1[i] - nums2[i]\n",
    "            if now in a:\n",
    "                res=max(res, i - a[now])\n",
    "            else:\n",
    "                a[now] = i\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        widest = 0\n",
    "        prefix_sum_map = {0: -1}  # 前缀和 -> 最小索引\n",
    "        \n",
    "        for i in range(n):\n",
    "            sum1 += nums1[i]\n",
    "            sum2 += nums2[i]\n",
    "            \n",
    "            diff = sum1 - sum2\n",
    "            \n",
    "            if diff in prefix_sum_map:\n",
    "                widest = max(widest, i - prefix_sum_map[diff])\n",
    "            else:\n",
    "                prefix_sum_map[diff] = i\n",
    "        \n",
    "        return widest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a=collections.Counter()\n",
    "        a[0]=-1\n",
    "        now=0\n",
    "        res=0\n",
    "        for i in range(len(nums1)):\n",
    "            now+=nums1[i]-nums2[i]\n",
    "            if now in a:\n",
    "                res=max(res,i-a[now])\n",
    "            else:\n",
    "                a[now]=i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        t = []\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            t.append(nums1[i] - nums2[i])\n",
    "\n",
    "        s = 0\n",
    "        m = {}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            s += t[i]\n",
    "            if s == 0:\n",
    "                res = i + 1\n",
    "                continue\n",
    "            if s in m:\n",
    "                res = max(res, i - m[s])\n",
    "            else:\n",
    "                m[s] = i\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        temp=[nums1[i]-nums2[i] for i in range(n)]\n",
    "        res=accumulate(temp,initial=0)\n",
    "        d=defaultdict(int)\n",
    "        ans=0\n",
    "        for i,k in enumerate(res):\n",
    "            if k in d:\n",
    "                ans=max(ans,i-d[k])\n",
    "            else :\n",
    "                d[k]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = [nums1[i] - nums2[i] for i in range(n)]\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        for i, j in enumerate(acc):\n",
    "            if j not in d:\n",
    "                d[j] = i \n",
    "            else:\n",
    "                ans = max(ans, i - d[j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 初始化前缀和\n",
    "        prefix_sum1 = [0]\n",
    "        prefix_sum2 = [0]\n",
    "        \n",
    "        # 计算nums1和nums2的前缀和\n",
    "        for num in nums1:\n",
    "            prefix_sum1.append(prefix_sum1[-1] + num)\n",
    "        \n",
    "        for num in nums2:\n",
    "            prefix_sum2.append(prefix_sum2[-1] + num)\n",
    "        \n",
    "        # 初始化哈希表和结果\n",
    "        diff_to_index = {}\n",
    "        result = 0\n",
    "        \n",
    "        # 遍历前缀和数组\n",
    "        for i in range(len(prefix_sum1)):\n",
    "            diff = prefix_sum1[i] - prefix_sum2[i]\n",
    "            \n",
    "            # 如果这个差值之前出现过，更新结果\n",
    "            if diff in diff_to_index:\n",
    "                result = max(result, i - diff_to_index[diff])\n",
    "            \n",
    "            # 如果这个差值没有出现过，记录其索引\n",
    "            if diff not in diff_to_index:\n",
    "                diff_to_index[diff] = i\n",
    "                \n",
    "        return result\n",
    "\n",
    "# 示例\n",
    "s = Solution()\n",
    "print(s.widestPairOfIndices([1,1,0,1], [0,1,1,0]))  # 输出应为3\n",
    "print(s.widestPairOfIndices([0,1], [1,1]))  # 输出应为1\n",
    "print(s.widestPairOfIndices([0], [1]))  # 输出应为0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        acc1, acc2 = list(accumulate(nums1)), list(accumulate(nums2))\n",
    "        acc = [0] + [x-y for x, y in zip(acc1, acc2)]\n",
    "        d = {}\n",
    "        for i, x in enumerate(acc):\n",
    "            if x in d: \n",
    "                ans = max(ans, i-d[x])\n",
    "            else:\n",
    "                d[x] = i\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
